package cn.cxq.learning.joseph;

/**
 * 单向环形链表解决约瑟夫环问题
 */
public class CircleSingleLinkedList {

    private Person first;

    public void init(int num){

        first = new Person(-1);
        Person cur = null;

        for (int i = 1; i <= num; i++) {

            Person person = new Person(i);

            if (first.no == -1){
                cur = person;
                first = person;
                person.nest = first;

            }else {
                cur.nest = person;
                person.nest = first;
                cur = person;
            }
        }
    }

    public void list(){
        Person cur = first;
        if (first.no == -1) {
            System.out.println("约瑟夫环为空~~~");
            return;
        }
        System.out.println(cur);
        while (cur.nest != first){
            cur = cur.nest;
            System.out.println(cur);
        }
    }

    public void joseph(int start, int term){

        if (this.first.no == -1){
            System.out.println("约瑟夫环为空~~~");
            return;
        }
        if (this.first.nest == this.first){
            System.out.println(this.first);
            return;
        }

        //移动到start位置作为开始
        for (int i = 0; i <start-1 ; i++) {
            first = first.nest;
        }

        //初始化辅助指针指向first前一个节点（方便单链表的删除）
        Person helper = this.first;

        while (helper.nest != first){
            helper = helper.nest;
        }

        //开始出环
        while (helper != first){
            for (int i = 0; i < term - 1; i++) {
                helper = helper.nest;
                first = first.nest;
            }
            System.out.println(first);

            helper.nest = first.nest;
            first = first.nest;
        }

        //最后一名：
        System.out.println("最后一个出圈的人：" + helper);
    }
}

class Person{
    int no;
    Person nest;

    @Override
    public String toString() {
        return "Person{" +
                "no=" + no +
                '}';
    }

    public Person(int no) {
        this.no = no;
        this.nest = null;
    }
}